package com.leetcode.algorithm.y22.m06;

/**
 * 1567. 乘积为正数的最长子数组长度
 * 
 * https://leetcode.cn/problems/maximum-length-of-subarray-with-positive-product/
 * 
 * @author jie.deng
 *
 */
class Question1567Solution02 {

	public int getMaxLen(int[] nums) {
		int len = nums.length;
		int[][] dp = new int[len][2];
		// dp[i][0]以 nums[i] 结尾，乘积为正的最长子数组的长度
		// dp[i][1]以 nums[i] 结尾，乘积为负的最长子数组的长度
		dp[0][0] = nums[0] > 0 ? 1 : 0;
		dp[0][1] = nums[0] < 0 ? 1 : 0;

		for (int i = 1; i < len; i++) {
			if (nums[i] == 0) {
				dp[i][0] = 0;
				dp[i][1] = 0;
			} else if (nums[i] > 0) {
				dp[i][0] = dp[i - 1][0] + 1;
				dp[i][1] = dp[i - 1][1] > 0 ? dp[i - 1][1] + 1 : 0;
			} else {
				dp[i][0] = dp[i - 1][1] > 0 ? dp[i - 1][1] + 1 : 0;
				dp[i][1] = dp[i - 1][0] + 1;
			}
		}

		int maxLen = dp[0][0];
		for (int i = 1; i < len; i++) {
			maxLen = Math.max(maxLen, dp[i][0]);
		}
		return maxLen;
	}

}